Chapter 1 Network Analysis
Networks are abstract structures used to represent patterns of relationships among sets of various “things” (Ajorlou 2018). Such structures can be used to represent social connections, spatial patterns, ecological relationships, etc. In GIS, the elements that compose geospatial networks are geolocated – in other words: they have latitude and longitude values attached to them. Network analysis encompasses a series of techniques used to interpret information from those networks. This chapter introduces basic concepts for building, analyzing and applying spatial networks to real-world problems.
Learning Objectives
By the end of the chapter, students will be able:
- To understand what networks are and to identify the elements that compose them;
- To categorize different types of networks according to their topologies;
- To create spatial networks and learn how to apply them in various applications;
- To extract relevant information from spatial networks about the relationship between their elements, such as routes, distances and centralities.
Key Terms
Network analysis, Spatial networks, Graph theory
1.1 Introduction to graph theory
Graphs are the abstract language of networks (Systems Innovation 2015a). Graph theory is the area of mathematics that study graphs. By abstracting networks into graphs, one is able to measure different kinds of indicators that represents information about relationships that exist within a certain system. This is especially useful to assess the state of complex adaptive systems such as societies, cities, ecosystems, etc. All graphs are composed of two parts: nodes and edges.
1.1.1 Nodes
A node (or vertex) may represent any thing that can be connected with other things. For example, it can represent people in social networks, street intersections in road networks, or chemical compounds in molecular networks, among others.
1.1.2 Edges
Edges, on the other hand, represent how vertices are interconnected to each other. So it may represent the vertices’ social connections, street segments, molecular bindings, etc. The graph below represents rapid and frequent transit lines in Metro Vancouver. Each node represents a transit line and the edges represents connections between those lines.
Graph representing Metro Vancouver rapid and frequent transit network
.(images/metro_vancouver_transit_network.jpeg){.center}
1.2 Connectivity and order
There are two major types of connections within the graphs: directed and undirected. Connections are directed when they have a specific node of origin and destination.
1.2.1 Direct
Directed graphs are networks where the order of elements change relationships between them. We represent directed connections with an arrow. For example, in the case of the transit network we could use a directed graph to represent the path one has to take in order to shift from one line to another.
1.2.2 Undirect
On the other hand, in an undirected graph, connections are represented as simple lines instead of arrows. The order of elements does not matter.
1.3 Network topologies
Topology is the study of how network elements are arranged. The same elements arranged in different ways can change the network structure and dynamics. A very common example is the arrangement of computer networks (Wikibooks 2018).
1.3.1 Physical versus logical topology
In GIS we use networks to represent spatial structures of various kinds. While all networks can be represented in an abstract space - this is, without a defined position in the real-world - some network analysis might be more useful when we attach physical properties to them, such as latitude and longitude coordinates. We call logical topology the study of how network elements are arranged in this abstract space. On the other hand, physical topology refers to the arrangemet of networks in the physical space. We can then classify “types” of networks according to the way their nodes is arranged.
1.3.2 Non-hierarchical
1.3.2.1 Lines
Lines are when nodes are arranged in series where every node has no more than two connections, except for the two end nodes. A rail transit line, for example, can be represented as a line network. The map below portrays the SkyTrain Millenium Line in Vancouver. Each node represents a stop and the lines the connections between those stops.
1.3.2.2 Rings
Rings are similar to lines except that there are no end nodes. So each and every node has two connections and the “first” and “last” nodes are connected to each other forming a circle. The spatial structure of the Stanley park seawall trail in Vancouver resembles a ring. In this example, nodes stand for intersections and view spots and edges are the connections between these spots along the seawall.
1.3.2.3 Meshes
In a mesh, every node is also connected to more than one node. However, in this case nodes can be connected to more than two nodes. Connections in a mesh are non-hierarchical. Contrary to rings and lines where there is only one possible route from one node to another, in a mesh there are multiple routes to access other nodes in the network. A common way to generate a mesh network is using Delaunay triangulation (Wikimedia Foundation 2021), where nodes are connected in order to form triangles and maximize the minimum angle of all triangles. Mesh configurations are commonly used in decentralized structures such as the internet.
1.3.2.4 Fully connected
As the name suggests, in fully connected networks every node is connected to every other node. The graph representing all possible origin-destination commutes among Metro Vancouver municipalities is a type of fully connected network.
1.3.3 Hierarchical topologies
Different from non-hierarchical topologies, hierarchical configurations are structured around a central node or link.
1.3.3.1 Stars
Stars are hierarchical structures where two or more nodes are directly connected to a central node. This concentric garden at the University of British Columbia can be represented according to a star topology.
1.3.3.2 Buses
Buses are structures where every path from one node to another passes through a central path or corridor. If we isolate a street segment from an urban street network, the connections between buildings and streets depict a bus topology.
1.3.3.3 Trees
In tree topologies, nodes are structured from a root node and arranged into edges that are similar to branches of a tree. This highly hierarchical structure create a sort of parent - child relationship amongst nodes. The spatial configuration of boat marinas are usually structures in tree-like topologies. By definition, all tree network structures will always have more than one terminal nodes (a node that only has one connection to the network).
1.4 Spatial Network Analysis
Networks can then be arranged according to various different configurations. Aside from classifying networks into different types according to their topologies, some of the most useful features of spatial network analysis refers to how to extract information from these structures given certain parameters.
1.4.1 Network tracing
The act of modelling spatial networks is called Network tracing. When tracing a network it is important to bear in mind the direction with which information is added to the network, especially when this orientation information is important to further analyze flows and relationships within such structure. For example, when mapping hydrological networks to study its flows it might be useful to model rivers downstream as this is an important information to represent the dynamics of the network.
1.4.2 Linear referencing
Linear referencing systems are commonly used for finding the length of paths along the network (Ramsey 2012). In this method, locations are defined in terms of
1.4.3 Routing
1.4.3.1 Least cost paths
1.4.3.2 Least cost corridors
1.4.3.3 Reach analysis
Reach techniques are commonly used to find the incidence of defined elements within a certain radius from a chosen node. All possible routes are modeled. The number of terminal nodes varies according to the network structure. Urban walkability indices usually uses reach techniques to assess the intensity of certain indicators (such as intersection density or non-residential land uses) given a walkable radius (Martino 2020).
1.4.4 Network Centrality
Nodes and edges of a graph can be ranked in terms of how “important” they are to the overall network. Network centrality measures represent whether elements of a graph are more central or peripheral to the overall system. Such measures can then be interpreted as indicators of importance. Applications are endless. Centrality measures are used for ranking search engine pages [], for finding persons of interest in social networks [] and for modelling movement in street network []. There are several centrality measures that serve to the most various purposes. The most common ones are: Degree, Closeness and Betweenness centrality.
1.4.4.1 Degree centrality
The number of connections of each node.
1.4.4.2 Closeness centrality
How close the node is to every other node of the graph in logical distance.
1.4.4.3 Betweenness centrality
How likely a node or an edge is to be passed through when going from every node to every other node of the graph.